package nextGreaterElement;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = getNextBig(nums2);
        int []ans = new int[nums1.length];
        int index = 0;
        for (int num: nums1) {
            ans[index++] = map.getOrDefault(num,-1);
        }
        return ans;
    }
    private Map<Integer,Integer> getNextBig(int[] nums2){
        Map<Integer,Integer> map = new HashMap<>();
        // 单调栈获取每个元素的下一个更大的值
        Stack<Integer> stack = new Stack<>();
//        for (int i = 0; i < nums2.length; i++) {
//            while (!stack.isEmpty()&&nums2[stack.peek()]<nums2[i]){
//             map.put(nums2[stack.pop()],nums2[i]);
//            }
//            stack.push(i);
//        }

        // 没有重复元素
        for (int num: nums2) {
            while (!stack.isEmpty()&&stack.peek()<num){
                map.put(stack.pop(),num);
            }
            stack.push(num);
        }
        return map;
    }
}
